package com.coder.algorithm.leetcode

import java.util.*

/**
 * [430. 扁平化多级双向链表](https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/)
 *
 * @author yuhus
 * @date: 2022/4/8
 */
object l_0430 {
    class Node(var `val`: Int) {
        var prev: Node? = null
        var next: Node? = null
        var child: Node? = null
    }

    fun flatten(root: Node?): Node? {
        var curr = root
        var stack = Stack<Node>()
        while (curr != null) {
            if (curr.child != null) {
                if (curr.next != null) {
                    stack.push(curr.next)
                }
                // child -> next
                curr.child!!.prev = curr
                curr.next = curr.child
                curr.child = null

                curr = curr.next
            } else if (curr.next == null && stack.isNotEmpty()) {
                var next = stack.pop()
                curr.next = next
                next.prev = curr

                curr = next
            } else {
                curr = curr.next
            }
        }
        return root
    }
}